# List

[List](https://scala-lang.org/api/3.x/scala/collection/immutable/List.html)
представляет собой линейную неизменяемую последовательность.
Каждый раз, когда в список добавляются или удаляются элементы, по сути создается новый список из существующего.

Он обеспечивает быстрый 
([за постоянное время](https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0)) 
доступ как к первому элементу, так и к остальному списку, 
а также быструю операцию добавления нового элемента в начало списка. 
Большинство оставшихся операции занимают линейное время исполнения.

#### Создание списка

Список можно создать различными способами:

```dotty
val ints = List(1, 2, 3)
// ints: List[Int] = List(1, 2, 3)
val names = List("Joel", "Chris", "Ed")
// names: List[String] = List("Joel", "Chris", "Ed")
val namesAgain = "Joel" :: "Chris" :: "Ed" :: Nil
// namesAgain: List[String] = List("Joel", "Chris", "Ed")
```

При желании тип списка можно объявить, хотя обычно в этом нет необходимости:

```dotty
val ints: List[Int] = List(1, 2, 3)
// ints: List[Int] = List(1, 2, 3)
val names: List[String] = List("Joel", "Chris", "Ed")
// names: List[String] = List("Joel", "Chris", "Ed")
```

Одно исключение — когда в коллекции смешанные типы; в этом случае тип желательно указывать явно:

```dotty
val things: List[Any] = List(1, "two", 3.0)
// things: List[Any] = List(1, "two", 3.0)
```

#### Добавление элементов в список

Поскольку список неизменяем, в него нельзя добавлять новые элементы.
Вместо этого создается новый список с добавленными к существующему списку элементами.
Например, учитывая этот список:

```dotty
val a = List(1, 2, 3)
```

Для добавления одного элемента используется метод `::`, для добавления нескольких — `:::`, как показано здесь:

```dotty
val b = 0 :: a
// b: List[Int] = List(0, 1, 2, 3)
val c = List(-1, 0) ::: a
// c: List[Int] = List(-1, 0, 1, 2, 3)
```

Также можно добавить элементы в конец списка, но, поскольку список является односвязным,
следует добавлять к нему элементы только в начало;
добавление элементов в конец списка —
относительно медленная операция, особенно при работе с большими последовательностями.

> Если необходимо добавлять к неизменяемой последовательности элементы в начало и конец, используйте `Vector`.

Поскольку `List` является связанным списком,
крайне нежелательно пытаться получить доступ к элементам больших списков по значению их индекса.
Например, если есть `List` с миллионом элементов, доступ к такому элементу, как `myList(999_999)`,
займет относительно много времени, потому что этот запрос должен пройти почти через все элементы.
Если есть большая коллекция и необходимо получать доступ к элементам по их индексу,
вместо `List` используйте `Vector` или `ArrayBuffer`.

#### Как запомнить названия методов

В методах Scala символ `:` представляет сторону, на которой находится последовательность,
поэтому, когда используется метод `+:`, список нужно указывать справа:

```dotty
0 +: a
// res1: List[Int] = List(0, 1, 2, 3)
```

Аналогично, если используется `:+`, список должен быть слева:

```dotty
a :+ 4
// res2: List[Int] = List(1, 2, 3, 4)
```

Кроме того, хорошей особенностью этих символических имен методов является то, что они стандартизированы.
Те же имена методов используются с другими неизменяемыми последовательностями, такими как `Seq` и `Vector`.
Также можно использовать несимволические имена методов для добавления элементов
в начало (`a.prepended(4)`) или конец (`a.appended(4)`).

#### Как пройтись по списку

Представим, что есть список имён:

```dotty
val names = List("Joel", "Chris", "Ed")
```

Напечатать каждое имя можно следующим способом:

```dotty
for name <- names do println(name)
// Joel
// Chris
// Ed
```

Преимуществом использования циклов `for` с коллекциями заключается в том, что Scala стандартизирован,
и один и тот же подход работает со всеми последовательностями,
включая `Array`, `ArrayBuffer`, `List`, `Seq`, `Vector`, `Map`, `Set` и т. д.

#### Немного истории

Список Scala подобен списку из [языка программирования Lisp](https://en.wikipedia.org/wiki/Lisp_(programming_language)),
который был впервые представлен в 1958 году.
Действительно, в дополнение к привычному способу создания списка:

```dotty
val ints = List(1, 2, 3)
// ints: List[Int] = List(1, 2, 3)
```

точно такой же список можно создать следующим образом:

```dotty
val list = 1 :: 2 :: 3 :: Nil
// list: List[Int] = List(1, 2, 3)
```

Это работает, потому что `List` — односвязный список, оканчивающийся элементом `Nil`,
а `::` — это метод `List`, работающий как оператор "cons" в Lisp.


---

**Ссылки:**

- [Scala3 book](https://docs.scala-lang.org/scala3/book/taste-collections.html)
- [Scala3 book, Collections Types](https://docs.scala-lang.org/scala3/book/collections-classes.html)
- [Scala, Immutable collections](https://docs.scala-lang.org/ru/overviews/collections-2.13/concrete-immutable-collection-classes.html)
